package com.kobeliu.entity;

import java.util.*;

public class heapDemo {

    public static void main(String[] args) {

        int[] nums = {1,2,4,6,2,6,21,5,32,6,3};

        int[] ns = heapInsert(nums);

        int[] ns_heapify = heapify(ns);

        for (int i = 0; i < ns_heapify.length; i++) {
            System.out.println(ns_heapify[i]);
        }
    }

    private static int[] heapify(int[] ns) {

        int len = ns.length-1;
        int[] heapify = new int[ns.length-1];
        //把前数组的最后一个数放到头上做根
        heapify[0] = ns[ns.length-1];
        int p = 0;

        for (int i = 1; i < ns.length-1; i++) {
            heapify[i] = ns[i];
        }
        while(p < len){
            if((2*p+2) <= len-1){
                if(heapify[2*p + 1]>heapify[2*p + 2]){
                    if(heapify[p]<heapify[2*p+1]){
                        swap(heapify,p,2*p+1);
                        p = 2*p+1;
                    }else{
                        p = len;
                    }
                }else{
                    if(heapify[p]<heapify[2*p+2]){
                        swap(heapify,p,2*p+2);
                        p = 2*p+2;
                    }else{
                        p = len;
                    }
                }
            }else{
                p = len;
            }
        }

        return heapify;

    }



    private static int[] heapInsert(int[] nums) {

        int[] nums1 = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {
            nums1[i] = nums[i];
            if(i>0){
                int n = i;
                while(nums1[n]>nums1[(n-1)/2]){
                    swap(nums1,n,(n-1)/2);
                    n = (n-1)/2;
                }
            }
        }

        return nums1;

    }

    private static void swap(int[] nums1, int i, int j) {
        nums1[i] = nums1[i] ^ nums1[j];
        nums1[j] = nums1[i] ^ nums1[j];
        nums1[i] = nums1[i] ^ nums1[j];
    }

    public static int[] loudAndRich(int[][] richer, int[] quiet) {
        int n = quiet.length;
        Map<Integer, List<Integer>> map = new HashMap<>();
        int[] in = new int[n];
        for (int[] r : richer) {
            int a = r[0], b = r[1];
            List<Integer> list = map.getOrDefault(a, new ArrayList<>());
            list.add(b);
            map.put(a, list);
            in[b]++;
        }
        Deque<Integer> d = new ArrayDeque<>();
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = i;
            if (in[i] == 0) d.addLast(i);
        }
        while (!d.isEmpty()) {
            int t = d.pollFirst();
            for (int u : map.getOrDefault(t, new ArrayList<>())) {
                if (quiet[ans[t]] < quiet[ans[u]]) ans[u] = ans[t];
                if (--in[u] == 0) d.addLast(u);
            }
        }
        return ans;
    }
}
